package nan.Hash_Tree;

class BinarySearchNode{
    public int key;
    public int value;
    public BinarySearchNode left;
    public BinarySearchNode right;

    public BinarySearchNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
public class BinarySearchTree {
    private BinarySearchNode root=null;//通过root表示树的根节点，空树就使用空引用
    //这个方法用于根据key来找value
    public Integer get(int key){
        BinarySearchNode cur=root;
        while(cur!=null){
            if(key< cur.key){
                cur=cur.left;
            }else if(key>cur.key){
                cur=cur.right;
            }else{
                //key相等
                return cur.value;
            }
        }
        return null;
    }
    //这个方法用于插入新的节点
    public void put(int key,int value){
        //1.如果当前树是空，就把这个新节点作为根节点即可
        if(root==null){
            root=new BinarySearchNode(key, value);
            return;
        }
        //2.树不为空，找到该节点放到哪个位置上，查找过程要时刻记录父节点的位置
        BinarySearchNode cur=root;
        BinarySearchNode parent=null;
        while(cur!=null){
            if(key<cur.key){
                //往左子树找
                parent=cur;
                cur=cur.left;
            }else if(key> cur.key){
                //往右子树找
                parent=cur;
                cur=cur.right;
            }else{
                //key相等
                cur.value=value;
                return;
            }
        }
        //当while循环结束的时候，说明cur已经是空了，
        // 也就是找到合适的插入位置了，就是把当前节点插入到parent这个节点的子树上即可
        BinarySearchNode newNode=new BinarySearchNode(key, value);
        if(newNode.key< parent.key){
            parent.left=newNode;
        }else{
            parent.right=newNode;
        }
    }
    //删除
    public void remove(int key){
        BinarySearchNode cur=root;
        BinarySearchNode parent=null;
        while(cur!=null){
            if(key< cur.key){
                //往左子树找
                parent=cur;
                cur=cur.left;
            }else if(key> cur.key){
                //往右子树找
                parent=cur;
                cur=cur.right;
            }else{
                //key相等,cur节点就是待删除的节点
                removeNode(parent,cur);
                return;
            }
        }
    }//end remove;
    private void removeNode(BinarySearchNode parent,BinarySearchNode cur){
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            }else if(cur==parent.right){
                parent.right=cur.right;
            }else if(cur==parent.left){
                parent.left=cur.right;
            }
        }else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }else if(cur==parent.right){
                parent.right=cur.left;
            }else if(cur==parent.left){
                parent.left=cur.left;
            }
        }else{
            //要删除的节点左右子树都有
            //先在右子树中找到最小值
            BinarySearchNode goatParent=cur;
            BinarySearchNode goat=cur.right;
            while (goat.left!=null){
                goatParent=goat;
                goat=goat.left;
            }
            //把替罪羊的值赋给待删除节点
            cur.key=goat.key;
            cur.value=goat.value;
            if(goat==goatParent.left){
                goatParent.left=goat.right;
            }else{
                goatParent.right=goat.right;
            }
        }
    }
}